package multilevelLayoutPlugin;

import giny.model.Edge;
import giny.model.Node;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.List;
import java.util.TreeSet;
import java.util.UUID;
import java.util.Vector;

import cytoscape.CyEdge;
import cytoscape.CyNetwork;
import cytoscape.CyNode;
import cytoscape.Cytoscape;
import cytoscape.data.CyAttributes;
import cytoscape.data.Semantics;

public class Kruskal { 

	
/*	KRUSKAL'S ALGORITHM, PSEUDOCODE
	 * 
	 * 	 1  function Kruskal(G)
		 2    for each vertex v in G do
		 3      Define an elementary cluster C(v) <- {v}.
		 4    Initialize a priority queue Q to contain all edges in G, using the weights as keys.
		 5    Define a tree T <- empty       //T will ultimately contain the edges of the MST
		 6     // n is total number of vertices
		 7    while T has fewer than n-1 edges do
		 8      // edge u,v is the minimum weighted route from/to v
		 9      (u,v) <- Q.removeMin()
		10      // prevent cycles in T. add u,v only if T does not already contain a path between u and v. 
		11      // Note that the cluster contains more than one vertex only if an edge containing a pair of
		12      // the vertices has been added to the tree.
		13      Let C(v) be the cluster containing v, and let C(u) be the cluster containing u.
		14      if C(v) != C(u) then
		15        Add edge (v,u) to T.
		16        Merge C(v) and C(u) into one cluster, that is, union C(v) and C(u).
		17    return tree T

	 */


	public static CyNetwork findMaximalIndependentSet(CyNetwork previous, double level){
	
		// ITERATOR FOR THE EDGES AND THE NODES
		Iterator<CyNode> nodesIterator = previous.nodesIterator();
		
		int[] empty = {}; 
		
		// CREATE RESULT NETWORK "NEXT"
		CyNetwork next = Cytoscape.getRootGraph().createNetwork(empty, empty);
		HashSet<CyNode> nodesList = new HashSet<CyNode>(previous.getNodeCount());
		
		int count = 1;
		while(nodesIterator.hasNext()){
			CyNode n = nodesIterator.next();
			next.addNode(n);
			nodesList.add(n);
		}

		//add all the edges to next (except those having the same target and source, they don't affect the layout)
		Iterator<CyEdge> edgesIterator = previous.edgesIterator();
		while(edgesIterator.hasNext()){
			CyEdge e = edgesIterator.next();
			if(e.getTarget() != e.getSource()) {
				next.addEdge(e);
				
			}
		}

		CyAttributes nodesAttributes = Cytoscape.getNodeAttributes();

		// COMPUTE KRUSKAL WEIGHTS FOR THE NODES AND THE EDGES
		
		Hashtable<CyNode, Weights> weights =  computeWeights(nodesList, next, nodesAttributes);
		TreeSet<WeightedEdge> priorityQueue = computeWeights(previous.edgesList(), weights);			
		
		
		// CREATE PATH
		 
		KruskalEdges vv = new KruskalEdges();

        for (WeightedEdge edge : priorityQueue) {
            vv.insertEdge(edge);
        }

        
        Vector<Edge> edges = vv.getEdges();
        // HASH TABLE: SOURCE NODE -> EDGE
        Hashtable<Node, Edge> edgeTable1 = new Hashtable<Node, Edge>();
        // HASH TABLE: TARGET NODE -> EDGE
        Hashtable<Node, Edge> edgeTable2 = new Hashtable<Node, Edge>();

        for (Edge edge:edges){
        	edgeTable1.put(edge.getSource(), edge);
        	edgeTable2.put(edge.getTarget(), edge);
        }
        
        if (edges.size() == 0){
        	return next;
        }
        
        // START BROWSING THROUGH THE EDGES IN THE WEIGHT ORDER 
        
        Edge edge = edges.iterator().next();
        
        Node node1 = edge.getSource();
        Node node2 = edge.getTarget();
                
        HashSet<Node> freeEnds = new HashSet<Node>();

//		System.out.println("Kruskal Edges on level "+level+": "+edges.size()+"/"+previous.getEdgeCount());

		//while the list is not empty
		while(!edges.isEmpty()){

			if (nodesList.contains(node1) && nodesList.contains(node2))
				unite(node1, node2, nodesList, freeEnds, edge, edges, next, nodesAttributes);

			
    		node2 = null;
//    		if (freeEnds.size() > 0){
//    			node1 = freeEnds.iterator().next();
//    			freeEnds.remove(node1);
//        		edge = edgeTable1.get(node1);
//        		if (edge != null){
//        			node2 = edge.getTarget();
//        		}
//        		else {
//            		edge = edgeTable2.get(node1);
//    	    		if (edge != null){
//    	    			node2 = edge.getSource();
//    	    		}
//    	    		
//        		}
//    		}
//    		if (node2 == null){
       			if (!edges.isEmpty()) {
       				edge = edges.iterator().next();
           			edges.remove(edge);
        	        node1 = edge.getSource();
        	        node2 = edge.getTarget();		
       			}
//    		}


   		}//end while


//			if (WATCH == null){
//   			}
//   			else{
//   				System.out.println("The winner is "+WATCH.getIdentifier()+" with "+getConnectedEdges(WATCH, next).size()+" edges.");
//   				System.out.println("Alltogether "+next.getEdgeCount());
//   				System.out.println();
//   			}

		// REMOVE THE ONES WHICH WERE NOT COMBINED ON THIS LEVEL
		while (!nodesList.isEmpty()){
			CyNode node = nodesList.iterator().next();
			HashSet<Edge> e = getConnectedEdges(node, next);
			HashSet<Node> n = getNeighbouringNodes(node, e);
			Node pair2 = null;
			double value = Double.MAX_VALUE;
			for (Node nt: n){
				if (nodesList.contains(nt)){
					double weight = weight(node, nt, next, nodesAttributes);
					if (pair2 == null||weight < value) {
						pair2 = nt;
						value = weight;
					}
					
				}
			}
			if (pair2 == null) {
				remove(node, next, nodesAttributes);
				nodesList.remove(node);
			}
			else {
				edge = null;
				for (Edge et:e){
					if (et.getSource().getIdentifier().equals(pair2.getIdentifier())||
						et.getTarget().getIdentifier().equals(pair2.getIdentifier())){
						edge = et;
						break;
					}
				}
				if (edge == null) throw new RuntimeException();
//				System.out.println(nodesList.size());
				unite(node, pair2, nodesList,freeEnds,edge, edges, next, nodesAttributes);
			}
		}
		
		
		
		return next;

	}
	
	/** Removes the specified node from the network. The removed node
	 * is replaced by a new one. All the edges of this node are
	 * removed.
	 * 
	 * @param node The node to be removed.
	 * @param network The network.
	 * @param nodesAttributes The attributes related to the network.
	 */
	private static void remove(CyNode node, CyNetwork network, CyAttributes nodesAttributes){
		String idstr = UUID.randomUUID().toString();
		while(Cytoscape.getCyNode(idstr, false) != null){
			idstr = UUID.randomUUID().toString();
//			System.out.println("REMOVING "+idstr+" ");
		}
		CyNode newNode = Cytoscape.getCyNode(idstr, true);
		nodesAttributes.setAttribute(newNode.getIdentifier(), "ml_previous", new Integer(node.getRootGraphIndex()));
		//set weight
		int weight = 1;
		if(nodesAttributes.getIntegerAttribute(node.getIdentifier(), "ml_weight") != null){
			weight = nodesAttributes.getIntegerAttribute(node.getIdentifier(), "ml_weight");
		}
		nodesAttributes.setAttribute(newNode.getIdentifier(), "ml_weight", new Integer(weight));
//		System.out.println("Added new node"+newNode.getRootGraphIndex());
		
		//create edges from neighbors of pair1 to the new node

		replaceInNetwork(new Node[]{node}, newNode, network);
		
	
	}

//	private static Node WATCH;
	private static void replaceInNetwork(Node[] nodes, Node newNode, CyNetwork network ){
//		System.out.println("DOING REPLACEMENT!");
		network.addNode(newNode);

		HashSet<Node> addedNeighbours = new HashSet<Node>();
		for (Node n: nodes){

//			if (n.getIdentifier().equals("YKL112W"))
//				WATCH = newNode;
//
//			else if (n.equals(WATCH)){
//				WATCH = newNode;
//			}
				
			HashSet<Edge> edges = getConnectedEdges(n, network);
	
			HashSet<Node> neighbours =getNeighbouringNodes(n, edges);
			neighbours.removeAll(addedNeighbours);
			for (Node node:nodes){
				neighbours.remove(node);
			}

			network.removeNode(n.getRootGraphIndex(), false);

			addedNeighbours.addAll(neighbours);
			
			for(Node node : neighbours){
				CyEdge e = Cytoscape.getCyEdge(node, newNode, Semantics.INTERACTION, "", true, false);
				network.addEdge(e);
			}
	
			removeEdgesFromGraph(edges, network);
		}
		
	}


	/** Fetches the edges connected to the specified node within
	 * the given network.
	 * 
	 * This method throws an exception when the node has no edges
	 * (should never occur).
	 * 
	 * @param node The node to be explored.
	 * @param network The network context.
	 * @return A set of edges connected to the specified node.
	 */
	private static HashSet<Edge> getConnectedEdges(Node node, CyNetwork network){
		HashSet<Edge> edgesConnected = new HashSet<Edge>(); 
		int[] edgeIndices1 = network.getAdjacentEdgeIndicesArray(node.getRootGraphIndex(), true, true, true);
		if (edgeIndices1 == null) return edgesConnected;
		for(int i = 0; i < edgeIndices1.length; i++){
			edgesConnected.add(network.getEdge(edgeIndices1[i]));
		}
		return edgesConnected;
	}

	/** Fetches a set of neighbouring nodes of the specified node within
	 * the context of given edges.
	 * 
	 * @param node The node to be explored.
	 * @param edges List of available edges.
	 * @return set of nodes that are connected to the specified node by
	 * the specified edges.
	 */
	private static HashSet<Node> getNeighbouringNodes(Node node,HashSet<Edge> edges){
		HashSet<Node> neighboringNodes = new HashSet<Node>();
		for(Edge e : edges){
			if(e.getSource() != node && !neighboringNodes.contains(e.getSource())) neighboringNodes.add(e.getSource());
			if(e.getTarget() != node && !neighboringNodes.contains(e.getTarget())) neighboringNodes.add(e.getTarget());
		}
		return neighboringNodes;
	}
	
	/** Combines the two nodes in the context of given network.
	 * 
	 * @param node1 First pair to be combined.
	 * @param node2 Second pair to be combined.
	 * @param nodesList List of available nodes.
	 * @param freeEnds List of available free ends of the Kruskal path.
	 * @param edge
	 * @param edges
	 * @param next
	 * @param nodesAttributes
	 */
	private static  void unite(Node node1, Node node2, HashSet<CyNode> nodesList,HashSet<Node> freeEnds, Edge edge, Vector<Edge> edges, CyNetwork next, CyAttributes nodesAttributes){
		
//        	System.out.println(edge.getIdentifier());

		HashSet<Edge> edgesConnectedToPair1 = getConnectedEdges(node1, next);
		HashSet<Edge> edgesConnectedToPair2 = getConnectedEdges(node2, next);

		edges.remove(edge);
		edges.removeAll(edgesConnectedToPair1);
		edges.removeAll(edgesConnectedToPair2);
		
		next.removeEdge(edge.getRootGraphIndex(), false);


		freeEnds.addAll(getNeighbouringNodes(node1, edgesConnectedToPair1));
		freeEnds.addAll(getNeighbouringNodes(node2, edgesConnectedToPair2));

		freeEnds.remove(node1);
		freeEnds.remove(node2);
				
		//create a new node with weight of pair1.weight + pair2.weight and add it to next
		//generate random ID
		
		Node combinedNode = createCombinedNode(node1, node2, nodesAttributes);
		replaceInNetwork(new Node[]{node1, node2}, combinedNode, next);
		
		nodesList.remove(node1);
		nodesList.remove(node2);
	}
	
	/** Generates a combined node using the given two nodes. The
	 * new node as a random id. The weight attribute is computed
	 * as the sum of the ancestor nodes.
	 * 
	 * @param node1 	First node to be combined
	 * @param node2		Second node to be combined
	 * @param nodesAttributes The attributes.
	 * @return The combined node.
	 */
	private static Node createCombinedNode(Node node1, Node node2,
			CyAttributes nodesAttributes) {
		String idstr = UUID.randomUUID().toString();
		while(Cytoscape.getCyNode(idstr, false) != null){
			idstr = UUID.randomUUID().toString();
		}
		CyNode combinedNode = Cytoscape.getCyNode(idstr, true);
		int weight1 = 1;
		int weight2 = 1;
		if(nodesAttributes.getIntegerAttribute(node1.getIdentifier(), "ml_weight")!=null){
			weight1 = nodesAttributes.getIntegerAttribute(node1.getIdentifier(), "ml_weight");
		}
		if(nodesAttributes.getIntegerAttribute(node2.getIdentifier(), "ml_weight")!=null){
			weight2 = nodesAttributes.getIntegerAttribute(node2.getIdentifier(), "ml_weight");
		}
		nodesAttributes.setAttribute(combinedNode.getIdentifier(), "ml_weight", new Integer(weight1+weight2));
		nodesAttributes.setAttribute(combinedNode.getIdentifier(), "ml_ancestor1", new Integer(node1.getRootGraphIndex()));
		nodesAttributes.setAttribute(combinedNode.getIdentifier(), "ml_ancestor2", new Integer(node2.getRootGraphIndex()));
		return combinedNode;

	}

	/** removes the node from the graph and from the node list.
	 * 
	 * @param node1 The node to be removed.
	 * @param nodesList Node list.
	 * @param next The network.
	 */
	private static void removeNodeFromGraph(Node node1, HashSet<CyNode> nodesList, CyNetwork next) {
		nodesList.remove(node1);
		next.removeNode(node1.getRootGraphIndex(), false);
		
	}

	/** Removes the specified edge from the graph.
	 * @param edgesToRemove
	 * @param allEdges
	 * @param network
	 * @param node1
	 * @param freeEnds
	 */
	private static void removeEdgesFromGraph(HashSet<Edge> edgesToRemove, CyNetwork network) {
		for(Edge e: edgesToRemove){
			network.removeEdge(e.getRootGraphIndex(), false);
		}
	}

	private static Hashtable<CyNode, Weights> computeWeights(HashSet<CyNode> nodes, CyNetwork next, CyAttributes nodesAttributes){
		Hashtable<CyNode, Weights> weights = new Hashtable<CyNode, Weights>();
		for (CyNode node:nodes){
			
			weights.put(node, new Weights(node, next, nodesAttributes));
		}
		return weights;
		
	}

	private static TreeSet<WeightedEdge>  computeWeights(List<Edge> edges, Hashtable<CyNode, Weights> weights){
		
		TreeSet<WeightedEdge> priorityQueue = new TreeSet<WeightedEdge>();
		for (Edge edge:edges){
			WeightedEdge wEdge = new WeightedEdge(edge, weights);
			priorityQueue.add(wEdge);
		}
        
		return priorityQueue;
	}
	
	
	private static class WeightedEdge implements Comparable<WeightedEdge> {
		public final double totalWeight;
		public Weights weight1;
		public Weights weight2;
		public final Edge edge;
		public double degree;
		public double weight;
		
		public WeightedEdge(Edge edge, Hashtable<CyNode, Weights> weights){
			weight1 = weights.get(edge.getSource());
			weight2 = weights.get(edge.getTarget());
			
			weight = weight1.weight + weight2.weight;
			degree = weight1.degree + weight2.degree;
			this.edge = edge;
			totalWeight = weight1.total() + weight2.total();
			//orginal method by Walshaw:
			//totalWeight = weight;

		}
		
		@Override
		public int compareTo(WeightedEdge o) {

			if (o.totalWeight < totalWeight) return 1;
			else if (o.totalWeight > totalWeight) return -1;
			else if (o.degree > degree) return -1;
			else if (o.degree < degree) return 1;
//			else	if (o.totalWeight < totalWeight) return 1;
//				else if (o.totalWeight > totalWeight) return -1;
				
			return edge.hashCode() - o.edge.hashCode();
		}
	}
	
	private static double weight(Node node1, Node node2, CyNetwork network, CyAttributes attr){
		Weights n1 = new Weights(node1, network, attr);
		Weights n2 = new Weights(node2, network, attr);
		
		return n1.total() + n2.total();
	}
   	
 private static class Weights {
	public final double weight;
	public final double degree;
	
	public Weights(Node node, CyNetwork network, CyAttributes nodesAttributes){
		int[] edgeIndices = network.getAdjacentEdgeIndicesArray(node.getRootGraphIndex(), true, true, true);
		degree = edgeIndices.length;
		if (nodesAttributes.getIntegerAttribute(node.getIdentifier(), "ml_weight") != null)
			weight = nodesAttributes.getIntegerAttribute(node.getIdentifier(), "ml_weight");
		else 
			weight = 1;

	}
	
	public double total(){
		return 
		weight + 
		degree;
	}
	
}

 
 private static class KruskalEdges
 {
     Vector<HashSet<Node>> vertexGroups = new Vector<HashSet<Node>>();
     TreeSet<WeightedEdge> kruskalEdges = new TreeSet<WeightedEdge>();
     private HashSet <Node> endNodes = new HashSet<Node>();
     
     public Vector<Edge> getEdges()
     {
//    	 System.out.println("SIZE: "+kruskalEdges.size());
    	 Vector<Edge> edges = new Vector<Edge>();
    	 for (WeightedEdge e:kruskalEdges){
    		 edges.add(e.edge);
    	 }
         return edges;
     }
     HashSet<Node> getVertexGroup(Node vertex)
     {
         for (HashSet<Node> vertexGroup : vertexGroups) {
             if (vertexGroup.contains(vertex)) {
                 return vertexGroup;
             }
         }
         return null;
     }

     /**
      * The edge to be inserted has 2 vertices - A and B
      * We maintain a vector that contains groups of vertices.
      * We first check if either A or B exists in any group
      * If neither A nor B exists in any group
      *     We create a new group containing both the vertices.
      * If one of the vertices exists in a group and the other does not
      *     We add the vertex that does not exist to the group of the other vertex
      * If both vertices exist in different groups
      *     We merge the two groups into one
      * All of the above scenarios mean that the edge is a valid Kruskal edge
      * In that scenario, we will add the edge to the Kruskal edges    
      * However, if both vertices exist in the same group
      *     We do not consider the edge as a valid Kruskal edge
      */
     public void insertEdge(WeightedEdge edge)
     {
         Node vertexA = edge.edge.getSource();
         Node vertexB = edge.edge.getTarget();

         
         if (vertexA == vertexB) return;
         
         HashSet<Node> vertexGroupA = getVertexGroup(vertexA);
         HashSet<Node> vertexGroupB = getVertexGroup(vertexB);

         if (vertexGroupA == null) {
        	 endNodes.add(vertexA);
             kruskalEdges.add(edge);
             if (vertexGroupB == null) {
                 HashSet<Node> htNewVertexGroup = new HashSet<Node>();
                 htNewVertexGroup.add(vertexA);
                 htNewVertexGroup.add(vertexB);
                 vertexGroups.add(htNewVertexGroup);
                 endNodes.add(vertexB);
             }
             else {
                 vertexGroupB.add(vertexA);
                 endNodes.remove(vertexB);
             }
         }
         else {
             if (vertexGroupB == null) {
                 vertexGroupA.add(vertexB);
                 kruskalEdges.add(edge);
                 endNodes.add(vertexB);
            	 endNodes.remove(vertexA);
             }
             else if (vertexGroupA != vertexGroupB) {
                 vertexGroupA.addAll(vertexGroupB);
                 vertexGroups.remove(vertexGroupB);
                 kruskalEdges.add(edge);
                 endNodes.remove(vertexB);
            	 endNodes.remove(vertexA);
             }
         }
     }
     public HashSet<Node> getEndNodes(){
    	 return endNodes;
     }
 }

 
}

